package leetcode.周赛.第249场;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/7/11 10:36
 * @description：https://leetcode-cn.com/contest/weekly-contest-249/problems/unique-length-3-palindromic-subsequences/
 */
public class 长度为3的不同回文子序列 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.countPalindromicSubsequence("tlpjzdmtwderpkpmgoyrcxttiheassztncqvnfjeyxxp"));
        System.out.println(solution.countPalindromicSubsequence("nhzosdwmwomlebymvkbqbdohzdtpufnllwzhqptyffreebalphgsslryuqryloqxvbehtohdrsynmcbligczvoyzrhbtmqxepqmcjirwishyvoliizknzrokejtqtfoylsdzpgeooczxldvmsnhvzgojxnwwhukynvhhpzmdoiooliesogubtsvkrvzmanpwwlnlskremzisqwwwjistwabqxztlcqwlsxbuhjdnouecwqgxdlggauxrelipqlgvfkmgoozhzrhortbpmxhupjqqrsrvqxqilptchtedoznxvgvmuticzdzwszzujuanlrrpvycgawoxfbvxhkdyhmcxdlrtyktekcmkyajlywcrozjkedwlrqpaugdobtffwidxawddgeraaugiebtntmuncnybuwnlzbmkrmxbcpbhqoiznlpcswqtsflfilkclrjdxbvcctvopoidjrtwszpjpfrfcvjtouvzvpqayvgesiiawokdqatfkijsuocbeqrhrmlhtclhrmrbkpahfdgiatejsnvubwbaxwooskcaiuqvxcvgpnkiiiencnxjsvvgdfptreumttlyoqqwqdblhhbnilbvbwwpnmouxlvqimdbcxisnegllnejhkipuqbcrhsrxwipdjzskpyijuvrvtrnqljjefymfdcvcuvwaitdjevuvelkrglhtlnivmvjyzmhjnzvudgqwocvwhthxdlyfljabngzjayvqudhvsdslacgvosnchhbkulcxpangdlpgkrczbnnzokmqzgauitqutiboveumsqvbulhbfbynzogtejuwi"));
    }

    /*
    class Solution {

        Set<String> set = new HashSet<>();
        String s;
        public int countPalindromicSubsequence(String s) {
            this.s = s;
            dfs(new StringBuilder(), 0);
            return set.size();
        }

        public void dfs(StringBuilder builder, int index) {
            if (builder.length() > 3) return;
            if (builder.length() == 3) {
                if (isOk(builder.toString())) {
                    set.add(builder.toString());
                    return;
                }
            }
            if (index >= s.length()) return;
            StringBuilder curBuilder = new StringBuilder(builder);
            //拿
            curBuilder.append(s.charAt(index));
            dfs(curBuilder, index + 1);
            //不拿
            dfs(builder, index + 1);
        }

        public boolean isOk(String str) {
            return str.charAt(0) == str.charAt(2);
        }
    }
     */

    class Solution {
        public int countPalindromicSubsequence(String s) {
            char[] chars = s.toCharArray();
            boolean[] booleans = new boolean[26];
            HashSet<String> set = new HashSet<>();
            StringBuilder builder = new StringBuilder(s);
            String reS = builder.reverse().toString();
            for (int i = 0; i < chars.length - 2; i++) {
                char prev = chars[i];
                if (booleans[prev- 'a']) continue;
                booleans[prev - 'a'] = true;
                int endIdx = s.length() - reS.indexOf(prev) - 1;
                for (int j = i + 1; j < endIdx; j++) {
                    StringBuilder builder1 = new StringBuilder();
                    builder1.append(prev);
                    builder1.append(s.charAt(j));
                    builder1.append(prev);
                    set.add(builder1.toString());
                }
            }
            return set.size();
        }
    }

}
